As devices for performing quantum computations mature, the need for efficient quantum compilation methods increases. While conventional quantum devices will require vast amounts of error correction to combat decoherence, certain two-dimensional quantum systems based on non-Abelian anyons, or quasiparticle excitations obeying non-Abelian statistics, will require little to no error correction. These systems are intrinsically protected against local errors by storing information globally rather than locally. When two quasiparticles are kept sufficiently far apart and braided adiabatically, a unitary evolution is realized. Such an evolution is called a braid of world lines, and such braids are topologically protected from local errors.
The use of non-Abelian anyons for topological quantum computation would allow intrinsic fault tolerance. For the so-called Fibonacci anyons, the state may be described by a fractional quantum Hall (FQH) plateau at filling fraction μ=12/5. In fact, it has been shown that in some cases, such anyons can realize universal quantum computation with braiding alone. Fibonacci anyons are thought to enable implementation of topological quantum computing. These quasiparticles allow quantum information to be natively topologically protected from decoherence and also allow a universal set of topologically protected quantum gates called “braiding matrices”, or “braids.”
Practical compilation (referred to herein also as decomposition or synthesis) of quantum circuits into braiding matrices has been an open topic until recently. Conventional compilation procedures are based on the Dawson-Nielsen implementation of the Solovay-Kitaev theorem, which states that any single-qubit quantum gate can be approximated to a desired precision ε using a circuit of depth
      O    ⁡          (                        ln          c                ⁡                  (                      1            ε                    )                    )        ,wherein c is approximately 3.97.
Methods have been previously developed for approximating a single-qubit unitary based on brute-force searches to find a braid with depth
      O    ⁡          (                        ln          c                ⁡                  (                      1            ε                    )                    )        ,where c=1, but require exponential time. The number of braids, however, grows exponentially with the depth of the braid, making this technique infeasible for long braids that are required to achieve a required precision. Thus, these methods are not practical for approximating single-qubit unitaries, and improved methods are needed. Disclosed herein are methods and apparatus that produce decompositions of single-qubit quantum gates into circuits drawn from the basis of Fibonacci anyon braid matrices such that circuit depth is
      O    ⁡          (                        ln          c                ⁡                  (                      1            ε                    )                    )        ,wherein c=1 and ε is the desired decomposition precision.